The present invention relates to the field of Markovian-sequence generation, that is, to methods and devices which generate sequences containing at least a portion having the Markov property. More particularly, the invention relates to a new type of Markovian-sequence generator and generation method with the ability to generate sequences including Markovian sequence portions whose properties are controllable.
There are many applications in which Markovian-sequence generators are used to generate sequences: often these applications seek to generate a Markovian sequence that will model a process (e.g. modelling a sequence of outcomes that could arise in a game of chance, modelling a process occurring in the natural world, etc.), other applications aim to compose a new work—for example a new melody, a new text work, etc.—notably, for the entertainment of the user. In the latter type of application it is often desirable for the composition process to be interactive, at least to a limited degree.
It is helpful to recall some basic features relating to Markovian sequences. A Markovian sequence (or Markov chain) is a sequence of items in which the items at locations early on in the sequence have no effect on the items at locations further on in the sequence. In a Markovian sequence of order 1, the next item in the sequence depends only on the item before it and on a set of probabilities that define the respective probabilities of transitions from one item to another. Each item in the sequence can be considered to represent a “system state” and the probability distribution defines the probability of transitions from one system state to another. For example, in the game of snakes and ladders, the sequence of squares landed on by a player's playing piece is a Markovian sequence of order 1. At each turn, the next square in the sequence is determined solely by the current square and the probabilities of different throws of a die
The “order” of a Markovian-sequence determines how many preceding items in a sequence are taken into account when the next item in the sequence is generated. For example, consider a Markovian-sequence generator which, so far, has produced a sequence of letters of the alphabet ABCEDDEG. When deciding the next letter of the sequence, a Markovian-sequence generator of order 1 would consider only the final item in the sequence (i.e. “G”), a Markovian-sequence generator of order 2 would consider the last two items in the sequence (i.e. the sub-sequence “EG”), a Markovian-sequence generator of order 3 would consider the last three items in the sequence (i.e. the sub-sequence “DEG”), and so on. For ease of description, the term “preamble” shall be used here to describe the item or sub-sequence that is taken into account by a Markovian-sequence generator when deciding what item to put next in a sequence. Thus, in the above example, preambles “G”, “EG” and “DEG” are used by the Markov generators of orders 1, 2 and 3, respectively. In each case, the Markovian-sequence generator determines the next item in the sequence by a random draw from among the possible candidate items that could, in theory, come next, taking into account the respective probability of each candidate item following on from the preamble in question.
The domain of items that can form part of the sequence, and the probabilities of transitions from one item to another, depend on the application in which the Markovian-sequence generator is being used. Usually, the domain of candidate items is substantially constant irrespective of the location within the sequence for which an item is being selected. Moreover, the items in the domain may be elements of different types, and/or elements of the same general type but having different properties: for example, in a case where the sequence to be generated will be a sequence of musical notes, the items in the domain can be notes having different pitches, durations, different rhythmic properties, different amplitudes, etc. and any combination thereof (i.e. different viewpoints).
In some cases the probabilities of transitions from one item to the next in the sequence are determined by explicit rules: for example, in the case where a Markovian sequence models the sequence of squares occupied by a playing piece during a game of snakes and ladders, the probability of a transition from a given square to a particular other square depends on the probability that a throw of a die will displace the playing piece onto that other square. However, in numerous applications, especially applications where a Markovian-sequence generator is intended to compose a new work automatically, the allowed transitions and their associated probabilities are usually derived from a training database which contains sequences or sub-sequences corresponding to the whole or parts of works of the type to be generated. In such a case, the Markovian-sequence generator is configured so that it applies transition probabilities only in respect of transitions that have already occurred in the sequences/sub-sequences in the training database.
Markov-chain text generators are often used to produce parodies of an input text (e.g. a parody of an input poem in the style of a particular poet). In such a case it is desirable for the output sequence to follow syntactical rules that are followed in the language of the text as well as mimicking stylistic tendencies of this particular input text. This is achieved by an analysis of the input text and control of the Markov-chain generator such that the probability of a given word-to-word transition in the generated text can be based on the probability of this same word-to-word transition in the input text. In a similar way, when it is desired to generate a melody in the style of a particular composer, musical phrases composed by that composer can be used as a training database for a Markovian-sequence generator, the note-to-note transitions in the generated melody being derived using a random draw based on the probability of the corresponding note-to-note transitions in the training database.
Conventional Markovian-sequence generators work on an incremental basis to build up a sequence item by item, using a random draw approach as described above. This is a “low-cost” approach, that is, one which allows the output sequence to be generated with little computational overhead. However, conventional Markovian-sequence generators do not allow the user to control the properties of the Markovian sequences that are produced.
European patent application EP 1,274,069 describes an automatic music-composition system, called the Continuator, which uses a Markovian-sequence generator to generate a sequence of musical notes or chords that is a continuation of a melody that is input to the system (e.g. by a user playing a musical instrument). The system seeks to generate a sequence which is a realistic-sounding continuation of a melody begun by the user and which mimics the stylistic characteristics of a training corpus. The Markovian-sequence generator used in the Continuator is a variable-order, Markovian-sequence generator which, when selecting the next note/chord to generate, compares the terminal portion of the melody so far (including the sequence played by the user and the continuation generated so far) with sequences present in the training corpus, looking for the longest sequence in the training corpus that matches with the terminal portion of the melody so far and selecting, as the next note/chord in the continuation, one which follows on from this longest sequence. This process is then iterated by considering the new sequence formed by the previous input sequence, concatenated to the items thus chosen (variable-length random walk approach)
The Continuator allows the user to launch the generation of a melody “in a particular direction”, for example in terms of the harmonic nature or velocity of the notes in the sequence, by inputting a short sequence of notes that is used to bias the choice of the next item to be included in the continuation. However, even in this system the user can exercise only very limited control over the sequence that is generated, in particular, the user's input affects only one item in the continuation (sequence) namely the item adjacent to the portion of the sequence that has already been generated.